package sjg.DataStructures.sort;

/**
 * 基础的算法时间复杂度衡量和示例代码
 */
public class BaseSortLearn {

    // 常数阶 O(1)
    // 执行时，消耗的时间并不随着某个变量的增长而增长
    private void test1() {
        int i = 1;
        int j = 2;
        ++i;
        j++;
        int m = i + j;
    }

    // 对数阶：O(log2n)
    // 2的x次方等于n，才结束， ==> 当循环log2n次以后，代码结束。 ==> 时间复杂度:O(log2n)
    // 现实中2时间上是根据代码变化的， ==> i*=3 ==> O(log3n)
    private void test2(int n) {
        int i = 1;
        while (i < n) {
            i *= 2;
        }
    }

    // 线性阶： O(n)
    // 循环体执行n遍。消耗时间随着n变化而变化。
    private void test3(int n) {
        int j;
        for (int i = 0; i <= n; i++) {
            j = 1;
            j++;
        }
    }

    // 线性对数阶： O(nlogN)
    // 将时间复杂度为O(logn)的代码循环N遍，它的时间复杂度就是 n*O(logn) ==> O(nlogn)
    private void test4(int n) {
        int m;
        for (int i = 0; i < n; i++) {
            m = 1;
            while (m < n) {
                i *= 2;
            }
        }
    }

    // 平方阶： O(n^2)
    // O(n) 的代码嵌套一层就是O(n^2)了。
    private void test5(int n) {
        int j;
        for (int x = 0; x <= n; x++) {
            for (int i = 0; i <= n; i++) {
                j = i;
                j++;
            }
        }
    }
}
